#include <iostream>
#include <assert.h>
using namespace std;

template <class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;
	pair<K, V> _kv;
	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(kv)
	{}
};

template <class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRl = subR->_left;
		Node* subp = parent->_parent;
		if(subRl)
		{
			subRl->_parent = parent;
		}
		subR->_left = parent;
		parent->_right = subRl;
		parent->_parent = subR;
		subR->_parent = subp;
		if (subp == nullptr)
		{
			_root = subR;
		}
		else if (parent == subp->_left)
		{
			parent->_left = subR;
		}
		else
		{
			parent->_right = subR;
		}
		parent->_bf = 0;
		subR->_bf = 0;
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* subp = parent->_parent;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;
		parent->_left = subLR;
		parent->_parent = subL;
		subL->_parent = subp;
		if (subp == nullptr)
		{
			_root = subL;
		}
		else if (subp->_left == parent)
		{
			subp->_left = subL;
		}
		else
		{
			subp->_right = subL;
		}
		parent->_bf = 0;
		subL->_bf = 0;
	}

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
		RotateR(parent->_right);
		RotateL(parent);
		if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		RotateL(parent->_left);
		RotateR(parent);
		if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	bool Insert(const pair<K, V>& kv)
	{
		Node* newnode = new Node(kv);
		if (_root == nullptr)
		{
			_root = newnode;
			return true;
		}
		Node* node = _root;
		Node* parent = nullptr;
		while (node)
		{
			if (node->_kv > kv)
			{
				parent = node;
				node = node->_left;
			}
			else if (node->_kv < kv)
			{
				parent = node;
				node = node->_right;
			}
			else
			{
				return false;
			}
		}
		if (parent->_kv > kv)
		{
			parent->_left = newnode;
			newnode->_parent = parent;
		}
		else
		{
			parent->_right = newnode;
			newnode->_parent = parent;
		}
		node->_parent = parent;
		while (parent)
		{
			if (newnode == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				newnode = newnode->_parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				if (parent->_bf == 2 && newnode->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == 2 && newnode->_bf == -1)
				{
					RotateR(parent);
				}
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}
private:
	Node* _root = nullptr;
};


//namespace bit
//{
//	// 适配器 -- 复用
//	template<class Iterator, class Ref, class Ptr>
//	struct Reverse_iterator
//	{
//		Iterator _it;
//	};
//	// vector和list反向迭代器实现
//	template<class Iterator, class Ref, class Ptr>
//	class vector_list
//	{
//		typedef Reverse_iterator<iterator, Ref, Ptr> T;
//		T operator++()
//		{
//			return _val--;
//		}
//
//		T operator++(int)
//		{
//			T ret = _val;
//			_val--;
//			return ret;
//		}
//
//		T operator--()
//		{
//			return ++_val;
//		}
//
//		T operator++(int)
//		{
//			T ret = _val;
//			_val++;
//			return ret;
//		}
//		T _val;
//	};
//}